package avl.recursion;

public class AVL {
    private Node root;

    public AVL(Node node) {
        root = node;
    }

    /**
     * 对外暴露的删除节点方法
     */
    public void delete(Node deleteNode) {
        root = delete(root, deleteNode);
    }

    /**
     * 合并删除某平衡节点后的两个子树
     */
    private Node mergeTwoTree(Node left, Node right) {
        if (left == null) {
            return right;
        }
        // left != null
        if (right == null) {
            return left;
        }
        // left != null && right != null
        // 右子树 高
        // 此时左右均不为空，高度均大于等于 1
        if (left.getHeight() < right.getHeight()) {
            if (right.getLeft() == null) {
                right.setLeft(left);
                return right;
            }
            Node tempRootParent = right;
            while (tempRootParent.getLeft().getLeft() != null) {
                tempRootParent = tempRootParent.getLeft();
            }
            Node tempRoot = tempRootParent.getLeft();
            tempRootParent.setLeft(null);
            tempRoot.setLeft(left);
            tempRoot.setRight(right);
            return tempRoot;
        } else {
            if (left.getRight() == null) {
                left.setRight(right);
                return left;
            }
            Node tempRootParent = left;
            Node tempRoot = left.getRight();
            Node tempRight;
            while ((tempRight = tempRoot.getRight()) != null) {
                tempRootParent = tempRoot;
                tempRoot = tempRight;
            }
            tempRootParent.setRight(null);
            tempRoot.setLeft(left);
            tempRoot.setRight(right);
            return tempRoot;
        }
    }

    private Node mergeTwoTreeByParent(Node parent) {
        return mergeTwoTree(parent.getLeft(), parent.getRight());
    }

    /**
     * 删除节点的递归方法 <br>
     * 严格来讲，这里的 deleteNode 应该是节点值，或者 Node 内 equals() 逻辑要重写
     *
     * @param root       树的根节点
     * @param deleteNode 要删除的节点
     * @return 删除后的树的根节点
     */
    private Node delete(Node root, Node deleteNode) {
        if (root == null) {
            // 或者抛出异常
            return null;
        }
        // 删除节点，如果重写了 equals 方法，这里应该是 root.equals(deleteNode)
        else if (root.getVal() == deleteNode.getVal()) {
            // 合并，返回
            Node node = mergeTwoTree(root.getLeft(), root.getRight());
            root = null;
            return node;
            // 或 return mergeTwoTreeByParent(root);
        }
        // 删除的节点在右子树
        if (root.getVal() < deleteNode.getVal()) {
            root.setRight(delete(root.getRight(), deleteNode));
            // 如果 root.left 为 null ，没必要计算高度差
            // 判断删右子树后，是否引起左子树高度比右子树高 2，
            if (root.getLeft() != null && getHeight(root.getLeft()) - getHeight(root.getRight()) == 2) {
                // 应该为根据高度判断第三节点，
                if (getHeight(root.getLeft().getLeft()) == getHeight(root.getLeft()) - 1) {
                    root = rightRotate(root);
                } else if (getHeight(root.getLeft().getRight()) == getHeight(root.getLeft()) - 1) {
                    root = doubleWithLeftChild(root);
                } else {
                    throw new IllegalArgumentException("树的高度计算出现错误");
                }
            }
        }
        // 删除的节点在左子树
        else {
            root.setLeft(delete(root.getLeft(), deleteNode));
            // 上边没有使用变量存放，因为感觉多一个变量，会更耗内存
            // 但不这样会增加方法调用，好像也消耗内存，而且还消耗时间
            Node right = root.getRight();
            if (right != null && getHeight(right) - getHeight(root.getLeft()) == 2) {
                // right != null 所以可以直接调用 .getHeight() 方法
                if (getHeight(right.getRight()) == right.getHeight() - 1) {
                    root = leftRotate(root);
                } else if (getHeight(right.getLeft()) == right.getHeight() - 1) {
                    root = doubleWithRightChild(root);
                } else {
                    throw new IllegalArgumentException("树的高度计算出现错误");
                }
            }
        }
        root.computerHeight();
        ;
        return root;
    }


    public void insert(Node newNode) {
        root = insert(root, newNode);
    }

    private Node insert(Node node, Node newNode) {
        if (node == null) {
            return newNode;
        }
        Node tempRoot = node;
        if (tempRoot.getVal() < newNode.getVal()) {
            tempRoot.setRight(insert(tempRoot.getRight(), newNode));
            if (tempRoot.getRight().getHeight() - getHeight(tempRoot.getLeft()) == 2) {
                if (tempRoot.getRight().getVal() < newNode.getVal()) {
                    tempRoot = leftRotate(tempRoot);
                } else {
                    tempRoot = doubleWithRightChild(tempRoot);
                }
            }
        } else {
            tempRoot.setLeft(insert(tempRoot.getLeft(), newNode));
            ;
            if (tempRoot.getLeft().getHeight() - getHeight(tempRoot.getRight()) == 2) {
                if (tempRoot.getLeft().getVal() < newNode.getVal()) {
                    tempRoot = doubleWithLeftChild(tempRoot);
                } else {
                    tempRoot = rightRotate(tempRoot);
                }
            }
        }
        tempRoot.computerHeight();
        return tempRoot;
    }

    private int getHeight(Node node) {
        return node == null ? 0 : node.getHeight();
    }

    /**
     * 左旋
     */
    private Node leftRotate(Node node) {
        Node tempRoot = node.getRight();
        node.setRightAndComputerHeight(tempRoot.getLeft());
        tempRoot.setLeftAndComputerHeight(node);
        return tempRoot;
    }

    /**
     * 右旋
     *
     * @param node
     * @return
     */
    private Node rightRotate(Node node) {

        Node tempRoot = node.getLeft();
        node.setLeftAndComputerHeight(tempRoot.getRight());
        tempRoot.setRightAndComputerHeight(node);
        return tempRoot;
    }

    /**
     * 左子树的双旋
     */
    private Node doubleWithLeftChild(Node node) {
        node.setLeft(leftRotate(node.getLeft()));
        Node tempRoot = rightRotate(node);
        return tempRoot;
    }

    private Node doubleWithRightChild(Node node) {
        node.setRight(rightRotate(node.getRight()));
        return leftRotate(node);
    }

    public void print() {
        TreeUtils.show(root);
    }

    public Node getRoot() {
        return root;
    }
}
